1. Field of the Invention
The present invention relates to descreening halftoned images and to printing a halftoned picture on different printers with different characteristics.
2. Background Description
Most printers today can print in only a limited number of colors. Digital halftoning is a technique for printing a picture (or more generally displaying it on some two-dimensional medium) using small dots with a limited number of colors such that it appears to consist of many colors when viewed from a proper distance. For example, a picture of black and white dots can appear to contain grey levels when viewed from some distance. For the sake of simplicity, the rest of the discussion will be restricted to the case of grayscale images and their rendering by black and white printers to facilitate the presentation, but those skilled in the art of digital halftoning will understand that the principles apply to color images as well. When we speak of ink, it could mean any material and/or mechanism which produces the black in the image, i.e., it could be toner for a xerographic printer, ink for an inkjet printer, etc.
We will be concerned with bilevel, fixed pixel size printers (for instance laser printers). Such printers have two fundamental characteristics:
1) The print resolution, say d dpi (dots per inch), which can be interpreted as saying that the intended fundamental units of the print are arranged on a grid of squares with each square or pixel of size 1/d inches by 1/d inches, where d typically varies from about 300 to about 3000. In some cases, the pixels lie on a rectangular grid, but since the discussion adapts equally well to this case, we will assume square pixels for definiteness. PA1 2) The dot gain which tells us how the actual printed pixel (or dot) differs from a perfect 1/d by 1/d square in shape and size (notice that in previous sentences, the word "dot" was used in a loose sense). While many printers perform differently, standard theory and much of the prior art on calibration, e.g., "MECCA-A Multiple-Error Correction Computation Algorithm for Bi-Level Image Hardcopy Reproduction", IBM Res. Rep., RZ1060 (1981) by P. Stucki, "Measurement of Printer Parameters for Model-based Halftoning", J. El. Imag., 2(3) (1993) 193-204, by T. N. Pappas, C. K. Dong and D. L. Neuhoff, and U.S. Pat. No. 5,649,073 to Knox, Hains and Sharma, assumes that printed dots can be reasonably described as round, say with diameter D (or as an ellipse in the case of a rectangular grid), and the dot gain is often described accordingly. PA1 one thinks of the image as covered by little squares of size 1/d by 1/d (also called pixels). PA1 each pixel p, can be designated by its horizontal ordering number i (say from left to right) and it vertical ordering number j (say from top to bottom). Thus, the location of p is specified by the pair (i,j). PA1 to the pixel at (i,j) one assigns the value g between 0 and 1, where 0 corresponds to white, 1 corresponds to black, and more generally, g corresponds to the grey level of this particular pixel. PA1 the matrix I is then defined by setting I(i,j)=g. PA1 The modeling consists of computing, for each pair (M,P) formed by a printing decision matrix M and a printer P with some printer characteristic, an approximation N.sub.1 to the matrix N. PA1 The averaging stage consists in using almost any preferred digital descreening technique, such as a good averaging technique, to get an approximation I' of I, but now using N.sub.1 instead of M to perform the descreening.
In the sequel, we make the assumption that no printed dot goes beyond a circle with diameter 2/d centered at the middle of the pixel where it is intended to be printed (a circular dot which covers an entire 1/d by 1/d square has diameter at least 2/d. This assumption is made to simplify the discussion and in particular the description of the invention. Adaptation to a more general case is tedious to describe but not difficult to implement by anyone skilled in the art of digital printing.
As taught in the invention disclosed in U.S. patent application Ser. No. 09/085,094 filed by A. R. Rao, G. R. Thompson, C. P. Tresser, and C. W. Wu on May 26, 1998, for "Microlocal Calibration of Digital Printers", both the probabilistic nature of individual dot printing and the way printing neighboring dots in various configurations affect the dot shapes can be captured by a calibration method. This method characterizes a printer by the probability distribution of what area of ink gets printed at each pixel depending on the configuration of dots to be printed in the neighborhood of that pixel (here we use the word "ink" as a generic name for what gets printed, such as ink or toner). In the sequel, whenever we speak of printer characteristic, we mean the characteristic as given by the method of calibration of digital printers, except where otherwise specified. The probabilistic nature of such printer characterization means in particular that the notation "fixed pixel size" for a printer refers to its idealized properties rather than to actual ones.
Consider now some grayscale image to be printed with a digital printer. We assume an image of size h by v, where h and v are expressed in inches to be consistent with the unit used in the dpi description. It is then convenient to interpret this image as a matrix, I, of size H=h.times.d by V=v.times.d in the following way:
Given a matrix such as I, a digital halftoning algorithm will associate to it an H by V halftone matrix M whose entries M.sub.(i,j) are either 0 or 1. Now 0 means that no dot will be printed by the digital printer at pixel (i,j), while a 1 means that a dot is to be printed.
A grayscale image can thus be considered as an array I of B-bit numbers, where typically B ranges from 4 to 12. Because M is an array of single bits of the same size as I, straightforward storage of M instead of I represents a factor B in compression. It often happens that the original grayscale image I is not available and only the halftone (or printing decision) matrix M is retained. Usually, because different printers have different characteristics, a given M will produce different images when used with two different printers. One solution to this problem is to generate an approximation to the original grayscale image I while taking into account the printer characteristics, P, and halftone this approximation taking into account the printer characteristics of a second printer. This invention discloses a method to generate this approximation.
The process of re-creating a grayscale image from a halftoned image is called descreening or inverse halftoning. In all rigor, inverse halftoning is more general since it does not presuppose that halftoning has been done with a screen (or dithering mask), but for brevity, we shall use "descreening" as an equivalent, general term. Early methods of descreening were optical, such as in U.S. Pat. No. 4,231,656 to Dickey et al. Digital methods based on matrices such as M, for instance in U.S. Pat. No. 4,630,125 to Roetling have been proposed, as well as digital methods using a scanned image, such as in European Patent Publication 301,786 to Crosfield or in U.S. Pat. No. 4,907,096 to Stanfield et al.
Because halfoning is based on the spatial integration properties of human vision, a common descreening process consists in (weighted) averaging of the grey levels in the neighborhood of each pixel (i,j) (for example, the neighborhood can be a rectangle centered at (i,j)). To have an image independent process, the averaging is done in the neighborhood of each pixel in the same way (except maybe the boundaries of the image). We shall assume a constant neighborhood and constant weights in the sequel for simplicity, but our invention adapts as well to the more general case. The size and shape of the neighborhood where averaging is performed (or NAP for short in the sequel) is quite crucial, in particular in the case when M has been obtained using a dithering mask. Original averaging methods used pre-determined fixed cell assumptions, which are clearly drawbacks, but as taught in the invention described in U.S. patent application Ser. No. 09/110,900 filed on Jul. 6, 1998, by G. R. Thompson, R. Rao and F. C. Mintzer for "Method and Apparatus for Repurposing Binary Images", the sole knowledge of M is enough to precisely recover the cell size for screened halftones. In the simplest cases, such masks have a single cell as a tiling unit of the image and each threshold level is represented once in the cell which has no further structure. Then, in the particular case of a uniform grey level, the descreened version of the halftone will be uniform (for all grey levels) if and only if the NAP is the same size as the cell. The invention disclosed in U.S. patent application Ser. No. 09/110,900 explains how to get the cell (hence the best NAP) from the sole knowledge of the matrix M if the mask is clustered, i.e., it has a tendency to group black dots. More sophisticated masks are multicell, where each cell tends to generate a dark halftone dot (made of several printed dots), in which case the good NAP should again be the cell, not the full mask. Again, the invention disclosed in U.S. patent application Ser. No. 09/110,900 explains how to get the cell (hence the best NAP) from the sole knowledge of the matrix M.
Methods not based on averaging have also been proposed, initially assuming the knowledge of the halftoning mask, such as in U.S. Pat. No. 4,630,125 to Roetling, but later without this drawback, for instance in U.S. Pat. No. 5,027,078 to Fan or in U.S. Pat. No. 5,384,684 to Seidner et al. We will present our invention in the context of averaging methods, but it applies as well to improving other methods.